package leetcode_core.leetcode_1;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class ThreeSum {
    public List<List<Integer>> threeSum(int[] nums) {
        return threeSumTarget(nums,0);
    }

    public List<List<Integer>> threeSumTarget(int[] nums,int target){
        //输入数组nums,返回所有和为target的三元组
        Arrays.sort(nums);
        int n = nums.length;
        List<List<Integer>> ans = new ArrayList<>();
        //穷举threeSum的第一个数
        for(int i = 0;i<n;i++){
            //对target-nums[i]计算twoSum
            List<List<Integer>> tuples = twoSumTarget(nums, target - nums[i], i + 1);
            //如果存在满足条件的二元组,再加上nums[i]就是符合条件的三元组
            for (List<Integer> tuple : tuples) {
                tuple.add(nums[i]);
                ans.add(new ArrayList<>(tuple));
            }
            //跳过第一个数字重复的情况,否则会出现重复的结果
            while(i<n-1 && nums[i] == nums[i+1]){
                i++;
            }
        }
        return ans;
    }

    /**
     *
     * @param nums
     * @param target
     * @param start
     * @return
     */
    List<List<Integer>> twoSumTarget(int[] nums,int target,int start){//左指针改为从start开始,其他不变
        List<List<Integer>> ans = new ArrayList<>();
        int left = start,right = nums.length-1;
        while(left<right){
            int sum = nums[left] + nums[right];
            int leftVal = nums[left];
            int rightVal = nums[right];
            //根据sum和target的比较,移动左右指针
            if(sum<target){
                while(left<right && nums[left] == leftVal){
                    left++;
                }
            }
            if(sum>target){
                while (left<right && nums[right] == rightVal){
                    right--;
                }
            }
            if(sum == target){
                List<Integer> t = new ArrayList<>();
                t.add(leftVal);t.add(rightVal);
                ans.add(t);
                //跳过所有的重复元素
                while(left<right && nums[left] == leftVal){
                    left++;
                }
                while (left<right && nums[right] == rightVal){
                    right--;
                }
            }
        }
        return ans;
    }



}
